//#region 并查集

/**并查集 示例模板。需要根据不同的需求进行修改。
 * - 注：join函数有不同的实现方式，不知道为什么
 * - 详细见： https://programmercarl.com/图论并查集理论基础.html#原理讲解
 * - 用处是判断 A B这两个元素是否同属于一个集合（
 * - 怎么判断呢？ 比如在把AB加入集合的时候，给他们设置一个相同的根元素，我们去判断的时候，看看他们根元素是否相同，就能判断是否同一个集合 
 * - 注意路径压缩：  https://programmercarl.com/图论并查集理论基础.html#路径压缩
 */
export class UnionFind {
    /**并查集 */ //节点数字作为下标，该下标的元素对应着该节点的根的下标
    father: number[] = []
    /**并查集 - 构造函数，在这里初始化
     * @param length 并查集长度。length根据题目中节点数量而定，一般比节点数量大一点就好
     */
    constructor(length: number) {
        this.father = Array.from<number, number>({ length }, (_, i) => i) //初始化时，每个节点都指向自己  
    }
    /**寻根。在寻根过程中会进行路径压缩。（理论见：https://programmercarl.com/图论并查集理论基础.html#路径压缩）
     * @param u 要寻找根的节点
     * @returns 返回根的值
     */
    find(u: number): number {
        if (u == this.father[u]) return u;//如果找到了根就返回结果  （根是指向自己的）
        // else return this.find(this.father[u]) //一层层寻根，没有压缩路径，不好
        else return this.father[u] = this.find(this.father[u]); // 没找到就递归寻找，并进行路径压缩  （让u直接指向根，下次寻找时间复杂度就是O(1) )
    }
    /**判断 u 和 v是否是同一个根 */
    isSame(u: number, v: number) {
        u = this.find(u);
        v = this.find(v);
        return u == v;
    }
    /**将v->u 这条边加入并查集。 
     * - 注：是把 u的根 和 v的根 相连，而不是直接相连这俩
     */
    join(u: number, v: number) {
        u = this.find(u); // 寻找u的根
        v = this.find(v); // 寻找v的根
        if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 
        this.father[v] = u;//把u的根放到v的根上 （而不是直接让u指向v） 
    }
}
/**1971. 寻找图中是否存在路径
 * - 无向图，n是节点数量
 * - edges二维数组的含义：edges[i][0]和edges[i][1]相连通
 * - 问 source 是否有到达 destination 的路径
 */
export function validPath(n: number = 3, edges: number[][] = [[0, 1], [1, 2], [2, 0]], source: number = 0, destination: number = 2): boolean {
    //并查集代码就是模板中的，无需修改，所以这里不写了

    const test = new UnionFind(n + 1)
    for (let i = 0; i < edges.length; i++) {
        test.join(edges[i][0], edges[i][1])
    }

    return test.isSame(source, destination)
}
/**547. 省份数量
 * - 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * - 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 * - 返回矩阵中 省份 的数量
 * - 总结：相连的节点用线连接起来，最后看“分成了几组”
 */
export function findCircleNum(isConnected: number[][] = [
    [1, 1, 1, 0, 1, 1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 0, 0, 0, 1, 0],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 1, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0, 0, 1, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
]): number {
    //并查集代码就是模板中的，无需修改，所以这里不写了

    /**矩阵的长宽 */
    const n = isConnected.length
    const union = new UnionFind(n)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j && isConnected[i][j] === 1) {//如果连通
                union.join(i, j)
            }
        }
    }
    console.log(union.father);

    //判断数组中有几个不同的元素。
    //注，需要在获取set的时候，给每个元素再调用一次find，做“路径压缩”，这样才能保证大家最终都能 直接 指向真正的终点！！
    const set = new Set(union.father.map((k) => union.find(k))) //利用set去重

    return set.size
}
/**684. 冗余连接
 * - edges原本是一个树，加了一条边后变成了一个“有环无向图”
 * - edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。 
 * - 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
 */
export function findRedundantConnection(edges: number[][] = [[1, 2], [1, 3], [2, 3]]): number[] {


    // 从前往后遍历，如果这两个点不在同一个集合，就join加入集合
    // 一旦遇到哪一组出现在集合里了，说明 如果再把这条边加入集合，就会导致出现环
    // 所以这一组数据就是我们要找的 “最后一条符合条件的边”，  （如果题目要求找第一个，就是从后往前遍历）


    const union = new UnionFind(edges.length)
    for (let i = 0; i < edges.length; i++) {
        if (union.isSame(edges[i][0], edges[i][1])) {
            return edges[i]
        } else {
            union.join(edges[i][0], edges[i][1])
        }
    }
    return []
}
/**685. 冗余连接 II
 * - edges原本是一个树，加了一条边后变成了一个“有环有向图”
 * - edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。 
 * - 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
 * - 注：删除之后需要仍然是一棵树（注意边是有向的）
 */
export function findRedundantDirectedConnection(edges: number[][] = [[1, 5], [3, 2], [2, 4], [4, 5], [5, 3]]): number[] {
    //这题与 I 的区别就是，这时候的边是有向边了！！
    //要求删除某条边，使得剩下的能构成一棵树！（每个节点最多一个父节点，且整个树只有一个根）
    // 注：[2,1] 代表2是1的父节点。即  2 --> 1
    //分为两种情况：
    // 1. 因为要求最多一个父节点，所以我们找“哪个节点入度为2（同时被两个箭头指向）”，删除它身上的某个即可 （不能单纯的直接删最后一个，不然可能导致构不成树变成孤立节点）
    // 2. 如果没有入度为二的节点，那么代码其实就和 684. 冗余连接 一样了


    const length = edges.length
    /**用来记录节点的入度。假设节点1的入度为2，那么就是这样：[x,2,x,x] */
    const inCount: number[] = new Array(length + 1).fill(0)
    for (let i = 0; i < length; i++) {
        inCount[edges[i][1]]++ // edges[i][1]是孩子节点
    }
    console.log(`inCount`, inCount)
    /**记录入度为2的边（如果有的话，就会出现两条边） 里面的元素是 edges 的索引（代表边）*/
    const two = []
    //然后从后往前判断，看看哪些入度为2
    for (let i = length - 1; i >= 0; i--) {
        if (inCount[edges[i][1]] === 2) {
            two.push(i)
        }
    }
    /**判断在入度为2的节点上，删除边 edges[index] 后，是否是一棵树
     * - 原理：用并查集判断，如果这个边在添加进去之前，就可以在并查集里找到了相同的根，那么这条边添加上之后，这个图一定不是树了
     * @param index edges的索引，代表一条边
     * @returns 布尔值
     */
    const isTreeAfterRemoveEdge = (index: number) => {
        const union = new UnionFind(length)
        for (let i = 0; i < length; i++) {
            if (i == index) continue;
            if (union.isSame(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
                return false;
            }
            union.join(edges[i][0], edges[i][1]);
        }
        return true;
    }

    if (two.length) {//如果有出现入度为2的节点，就选择删除其中一条边 
        if (isTreeAfterRemoveEdge(two[0])) {
            return edges[two[0]];
        } else {
            return edges[two[1]];
        }
    }

    //如果没有出现入度为2的点，那么说明随便删一个环的边都行。这时候就是 684. 冗余连接 的代码了
    const union = new UnionFind(length)
    for (let i = 0; i < length; i++) {
        if (union.isSame(edges[i][0], edges[i][1])) {
            return edges[i]
        } else {
            union.join(edges[i][0], edges[i][1])
        }
    }
    return []
}
/**2368. 受限条件下可到达节点的数目
 * https://leetcode.cn/problems/reachable-nodes-with-restrictions/description
 */
export function reachableNodes(n: number, edges: [number, number][], restricted: number[]): number {
    const restrictedSet = new Set(restricted)
    const union = new UnionFind(n)
    edges.forEach(([a, b]) => {
        if (restrictedSet.has(a) || restrictedSet.has(b)) return
        union.join(a, b)
    })
    //查找有谁的根和0的根是一样的，统计个数 （因为是无向图，所以只要和0根相同就行）
    let ans = 0;
    const fa = union.find(0);
    union.father.forEach((v) => {
        if (union.find(v) === fa) ans++
    })
    return ans;
}
//#endregion
